/**
 * yuhuan
 */
package com.yuhuan.data_structures;

/**
 * 二分查找
 * 给定一个有序的数组arr，查找key第一次出现的下标，不存在返回-1。
 * @author Guoyuhuan
 * @version 1.0
 */
public class BinarySearch {

    /**
     * 二分查找（非递归）
     * @param arr 在arr数组中查找
     * @param key 要查找的关键字
     * @return 和key相等的值在数组中所在的下标，若返回-1则表示未查找到
     */
    public static int binSearch(int[] arr,int key) {
        //初始化
        int num = -1;
        int mid = 0;
        int high = arr.length;
        int low = 0;
        //二分查找
        while(high>low) {
            mid = (low + high)/2;
            if(key == arr[mid]){
                num = mid;
                break;
            }
            else if(key < arr[mid]) {
                high = mid-1;
            }
            else {
                low = mid+1;
            }
        }
        return num;
    }
    /**
     * 二分查找（递归）
     * @param arr 在arr数组中查找
     * @param key 要查找的关键字
     * @param low 低位
     * @param high 高位
     * @return 与key相等的值在数组中所在的下标，若返回-1则表示未查找到
     */
    public static int binSearch2(int[] arr, int key,int low ,int high) {
        int mid = (low+high)/2;
        if(key>arr[mid]&&low<high)
            return binSearch2(arr,key,mid+1,high);
        else if (key<arr[mid]&&low<high) {
            return binSearch2(arr,key,low,mid-1);
        }
        else if (low<high) {
            return mid;
        }
        else {
            return -1;
        }
    }

    public static void main(String[] args) {
        int[] a = new int[]{1,2,4,5,6,22,23,24,55};
        System.out.println("球的数字："+binSearch(a, 24));//非递归   7
        System.out.println("2："+binSearch2(a, 24, 0, 8)); //递归 7
        System.out.println("l拉拉");
    }
}
